package com.leetcode.search.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/27 8:50
 */
public class RestoreIpAddresses_93 {

    private List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.equals("")) return res;
        backtrack(0, new StringBuilder(), s);
        return res;
    }

    private void backtrack(int nums, StringBuilder tempAddress, String s) {
        if (nums == 4 || s.length() == 0) {
            if (nums == 4 && s.length() == 0)
                res.add(tempAddress.toString());
            return;
        }
        for (int i = 0; i < s.length() && i <= 2; i++) {
            // 以0开头的数字需要排除
            if (i != 0 && s.charAt(0) == '0') break;
            String part = s.substring(0, i + 1);
            // 注意这里不能用part.compareTo("255")
            // 如果是4位数1开头的话，也会返回-1
            if (Integer.parseInt(part) <= 255) {
                if (tempAddress.length() != 0)
                    part = "." + part;
                tempAddress.append(part);
                // 削减了原始数字串
                backtrack(nums + 1, tempAddress, s.substring(i + 1));
                // 同时删除数字和 .
                tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
            }
        }
    }

}
